/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-03-30 10:23:41
 * @LastEditors: lily
 * @LastEditTime: 2021-04-28 10:21:07
 */
/*
 * @lc app=leetcode.cn id=17 lang=javascript
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start
/**
 * @param {string} digits
 * @return {string[]}
 */

//  思路：回溯法
//  数字串“翻译”成字母串，找出所有的翻译可能。
//  翻译每一个数字都有 3或4 种选择，从首位翻译到末位，会展开成一棵递归树。指针 i 是当前考察的字符的索引。
//  当指针越界时，此时生成了一个解，加入解集，结束当前递归，去别的分支，找齐所有的解。
//  https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/shou-hua-tu-jie-liang-chong-jie-fa-dfshui-su-bfsya/

//  复杂度：O(3^m × 4^n)  O(m+n)

var letterCombinations = function (digits) {
    if (digits.length == 0) return []
    let res = []
    const map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    // curStr是当前字符串，i是扫描的指针，表示现在“翻译”到第i个数字，基于此继续“翻译”
    var dfs = (curStr, i) => {
        // 指针越界，递归的出口
        if (i > digits.length - 1) {
            // 将解推入res
            res.push(curStr)
            // 结束当前递归分支
            return
        }
        // 当前数字对应的字母
        let letters = map[digits[i]]
        // 一个字母是一个选择，对应一个递归分支
        for (let letter of letters) {
            // 递归：选择letter，生成新字符串，i指针右移继续翻译
            dfs(curStr + letter, i + 1)
        }
    }
    // 递归的入口，初始字符串为''，从下标0开始翻译
    dfs('', 0)
    return res
};
// @lc code=end

console.log(letterCombinations("23"))